/*
 * @lc app=leetcode.cn id=40 lang=cpp
 *
 * [40] 组合总和 II
 */
#include <algorithm>
#include <vector>
using std::vector;

// @lc code=start
class Solution
{
    void combinationSum2_dfs(vector<int> &candidates, int target, int start, std::vector<int> &choice, std::vector<std::vector<int>> &res)
    {
        if (target == 0) {
            res.push_back(choice);
            return;
        }

        std::vector<bool> visited(candidates.size(), false);
        for (int i = start; i < candidates.size(); ++i) {
            int new_target = target - candidates[i];

            /* 因为candidates已经排完序了，如果target减去当前下标成员的值都小于0，那么后面的一定小于0，可以直接break */
            if (new_target < 0) {
                break;
            }
            if (!visited[candidates[i]]) {
                visited[candidates[i]] = true;
                choice.push_back(candidates[i]);
                /* 每次都从i的下一个下标开始遍历 */
                combinationSum2_dfs(candidates, new_target, i + 1, choice, res);
                choice.pop_back();
            }
        }
    }

  public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        vector<int> choice;
        /* 先将数组排个序，排完序之后，数组中的成员从小到大排列 */
        std::sort(candidates.begin(), candidates.end());
        combinationSum2_dfs(candidates, target, 0, choice, res);
        return res;
    }
};
// @lc code=end
